package main.java.indi.zyj.sword;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class Checkout {

    Queue<Integer> A;
    // 维持最大单调队列
    Deque<Integer> B;

    public Checkout() {
        A = new LinkedList<>();
        B = new LinkedList<>();
    }
    
    public int get_max() {
        return B.isEmpty() ? -1 : B.peekFirst();
    }
    
    public void add(int value) {
        A.offer(value);
        while (!B.isEmpty() && B.peekLast() < value) {
            B.removeLast();
        }
        B.offerLast(value);
    }
    
    public int remove() {
        if(A.isEmpty()) return -1;
        if(A.peek().equals(B.peekFirst()))
            B.pollFirst();
        return A.poll();
    }
}